package dp.二维数组;


/**
 * https://leetcode.cn/problems/minimum-path-sum/
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247489499&idx=1&sn=823fcd4097d78d8f4513f3a4d47b2a50&scene=21#wechat_redirect
 *
 * https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493739&idx=1&sn=b18c90adba28b227103f4c92e272c62b&chksm=9bd41663aca39f75b6b2a7d161283822b4268b05e9c3a9386d4a2567d2737c759d1f606862a6&scene=178&cur_album_id=2165181514903355392#rd
 *
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
 */
public class _64_最小路径和 {

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {1,3,1},{1,5,1},{4,2,1}
        };

        _64_最小路径和 _64_最小路径和 = new _64_最小路径和();
        int result = _64_最小路径和.minPathSum(grid);
        System.out.println(result);
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        meno = new int[m][n];
        return dfs(grid, m - 1, n - 1);
    }

    int[][] meno;

    private int dfs(int[][] grid, int i, int j) {
        if (i == 0 && j == 0) return grid[0][0];

        if (i < 0 || j < 0) return Integer.MAX_VALUE;

        if (meno[i][j] > 0) return meno[i][j];

        meno[i][j] = Math.min(dfs(grid, i - 1, j), dfs(grid, i, j - 1)) + grid[i][j];
        return meno[i][j];
    }
}
